package com.yjc.dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 *
 * @author yjc
 * @create 2024-08-08 15:55
 */
public class Subject_13 {
    public static void main(String[] args) {
        int n = 3;

        List<String> resList = new ArrayList<>();
        dfs(resList, n, n, "");

        System.out.println(resList);


    }

    private static void dfs(List<String> resList, int left, int right, String res) {
        if (left == 0 && right == 0) {
            resList.add(res);
            return;
        }
        //左括号已用完，继续使用右括号
        if (left < 0) {
            return;
        }

        //如果右括号数量大于左括号（这里的小于相当于右括号存在的数量大于左括号的），表明当前括号格式无效
        if (right < left) {
            return;
        }

        //加左括号
        dfs(resList, left - 1, right, res + "(");
        //加右括号
        dfs(resList, left, right - 1, res + ")");
    }
}
